﻿/*
 * This file is part of MonoStrategy.
 *
 * Copyright (C) 2010-2011 Christoph Husse
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Affero General Public License as
 *  published by the Free Software Foundation, either version 3 of the
 *  License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Affero General Public License for more details.
 *
 *  You should have received a copy of the GNU Affero General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Authors: 
 *      # Christoph Husse
 * 
 * Also checkout our homepage: http://monostrategy.codeplex.com/
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MonoStrategy
{
    internal interface IQueueItem
    {
        int Index { get; set; }
        Double F { get; }
    }

    internal class PriorityQueue<PathNodeKey> where PathNodeKey : IQueueItem
    {
        private List<PathNodeKey> InnerList = new List<PathNodeKey>();

        internal PriorityQueue()
        {
        }

        protected void SwitchElements(int i, int j)
        {
            PathNodeKey ik = InnerList[i];
            PathNodeKey jk = InnerList[j];

            ik.Index = j;
            jk.Index = i;

            InnerList[i] = jk;
            InnerList[j] = ik;
        }

        protected virtual int OnCompare(int i, int j)
        {
            PathNodeKey ik = InnerList[i];
            PathNodeKey jk = InnerList[j];

            if (ik.F < jk.F)
                return -1;
            else if (ik.F > jk.F)
                return 1;
            else
                return 0;
        }

        /// <summary>
        /// Push an object onto the PQ
        /// </summary>
        /// <param name="O">The new object</param>
        /// <returns>The index in the list where the object is _now_. This will change when objects are taken from or put onto the PQ.</returns>
        internal int Push(PathNodeKey item)
        {
            int p = InnerList.Count, p2;
            item.Index = InnerList.Count;
            InnerList.Add(item); // E[p] = O

            do
            {
                if (p == 0)
                    break;
                p2 = (p - 1) / 2;
                if (OnCompare(p, p2) < 0)
                {
                    SwitchElements(p, p2);
                    p = p2;
                }
                else
                    break;
            } while (true);
            return p;
        }

        /// <summary>
        /// Get the smallest object and remove it.
        /// </summary>
        /// <returns>The smallest object</returns>
        internal PathNodeKey Pop()
        {
            PathNodeKey result = InnerList[0];
            int p = 0, p1, p2, pn;
            PathNodeKey i0 = InnerList[InnerList.Count - 1];

            i0.Index = 0;
            InnerList[0] = i0;

            InnerList.RemoveAt(InnerList.Count - 1);

            result.Index = -1;

            do
            {
                pn = p;
                p1 = 2 * p + 1;
                p2 = 2 * p + 2;
                if (InnerList.Count > p1 && OnCompare(p, p1) > 0) // links kleiner
                    p = p1;
                if (InnerList.Count > p2 && OnCompare(p, p2) > 0) // rechts noch kleiner
                    p = p2;

                if (p == pn)
                    break;
                SwitchElements(p, pn);
            } while (true);

            return result;
        }

        /// <summary>
        /// Notify the PQ that the object at position i has changed
        /// and the PQ needs to restore order.
        /// </summary>
        internal void Update(PathNodeKey item)
        {
            int count = InnerList.Count;

            // usually we only need to switch some elements, since estimation won't change that much.
            while ((item.Index - 1 >= 0) && (OnCompare(item.Index - 1, item.Index) > 0))
            {
                SwitchElements(item.Index - 1, item.Index);
            }

            while ((item.Index + 1 < count) && (OnCompare(item.Index + 1, item.Index) < 0))
            {
                SwitchElements(item.Index + 1, item.Index);
            }
        }

        /// <summary>
        /// Get the smallest object without removing it.
        /// </summary>
        /// <returns>The smallest object</returns>
        internal PathNodeKey Peek()
        {
            if (InnerList.Count > 0)
                return InnerList[0];
            return default(PathNodeKey);
        }

        internal void Clear()
        {
            InnerList.Clear();
        }

        internal int Count
        {
            get { return InnerList.Count; }
        }
    }

}
